490. The Maze
Medium

There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.

You may assume that the borders of the maze are all walls (see examples).

 

Example 1:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

Example 2:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

Example 3:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: false

 

Constraints:

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1.
  • start.length == 2
  • destination.length == 2
  • 0 <= startrow, destinationrow <= m
  • 0 <= startcol, destinationcol <= n
  • Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
  • The maze contains at least 2 empty spaces.
Accepted
89,375
Submissions
167,878
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 3.88 (72 votes)

Solution


We can view the given search space in the form of a tree. The root node of the tree represents the starting position. Four different routes are possible from each position i.e. left, right, up or down. These four options can be represented by 4 branches of each node in the given tree. Thus, the new node reached from the root traversing over the branch represents the new position occupied by the ball after choosing the corresponding direction of travel.

Maze_Tree

In order to do this traversal, one of the simplest schemes is to undergo depth first search. In this case, we choose one path at a time and try to go as deep as possible into the levels of the tree before going for the next path. In order to implement this, we make use of a recursive function dfs(maze, start, desination, visited). This function takes the given mazemaze array, the startstart position and the destinationdestination position as its arguments along with a visitedvisited array. visitedvisited array is a 2-D boolean array of the same size as that of mazemaze. A True value at visited[i][j]visited[i][j] represents that the current position has already been reached earlier during the path traversal. We make use of this array so as to keep track of the same paths being repeated over and over. We mark a True at the current position in the visitedvisited array once we reach that particular positon in the mazemaze.

From every startstart position, we can move continuously in either left, right, upward or downward direction till we reach the boundary or a wall. Thus, from the startstart position, we determine all the end points which can be reached by choosing the four directions. For each of the cases, the new endpoint will now act as the new start point for the traversals. The destination, obviously remains unchanged. Thus, now we call the same function four times for the four directions, each time with a new start point obtained previously.

If any of the function call returns a True value, it means we can reach the desination.

The following animation depicts the process:

Current
1 / 10

Complexity Analysis

  • Time complexity : O(mn)O(mn). Complete traversal of maze will be done in the worst case. Here, mm and nn refers to the number of rows and coloumns of the maze.

  • Space complexity : O(mn)O(mn). visitedvisited array of size mnm*n is used.


Algorithm

The same search space tree can also be explored in a Depth First Search manner. In this case, we try to explore the search space on a level by level basis. i.e. We try to move in all the directions at every step. When all the directions have been explored and we still don't reach the destination, then only we proceed to the new set of traversals from the new positions obtained.

In order to implement this, we make use of a queuequeue. We start with the ball at the startstart position. For every current position, we add all the new positions possible by traversing in all the four directions(till reaching the wall or boundary) into the queuequeue to act as the new start positions and mark these positions as True in the visitedvisited array. When all the directions have been covered up, we remove a position value, ss, from the front of the queuequeue and again continue the same process with ss acting as the new startstart position.

Further, in order to choose the direction of travel, we make use of a dirdir array, which contains 4 entries. Each entry represents a one-dimensional direction of travel. To travel in a particular direction, we keep on adding the particular entry of the dirsdirs array till we hit a wall or a boundary. For a particular start position, we do this process of dirdir addition for all all the four directions possible.

If we hit the destination position at any moment, we return a True directly indicating that the destinationdestination position can be reached starting from the startstart position.

The following animation depicts the process:

Current
1 / 15

Complexity Analysis

  • Time complexity : O(mn)O(mn). Complete traversal of maze will be done in the worst case. Here, mm and nn refers to the number of rows and coloumns of the maze.

  • Space complexity : O(mn)O(mn). visitedvisited array of size mnm*n is used and queuequeue size can grow upto mnm*n in worst case.

Report Article Issue

Comments: 44
edaengineer's avatar
Read More

@vinod23

why does DFS TLE but not BFS when time complexity is same???

60
Show 5 replies
Reply
Share
Report
earthaa's avatar
Read More

Actually, DFS solution will not cause TLE error. You can copy the code and it will pass

28
Show 2 replies
Reply
Share
Report
leduykhanh's avatar
Read More

Very concise DFS solution :

class Solution {
    private int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        return dfs(maze, visited, start, destination);
    }
    
    private boolean dfs(int[][] maze, boolean[][] visited, int[] c, int[] des) {
        if (visited[c[0]][c[1]]) return false;
        if (c[0] == des[0] && c[1] == des[1]) return true;
        
        visited[c[0]][c[1]] = true;
        boolean result = false;
        for (int[] d : dir) {
            int x = c[0] + d[0];
            int y = c[1] + d[1];
            while ( 0 <= x && x < maze.length && 0 <= y && y < maze[0].length && maze[x][y] == 0) {
                x += d[0];
                y += d[1];
            }
            result = result || dfs(maze, visited, new int[]{ x - d[0], y - d[1]}, des);
        }
        return result;
    }
}

26
Show 3 replies
Reply
Share
Report
mithuntm's avatar
Read More

I can see that the solutions above are incorrect. If we are not considering the direction from which we are coming from, we won't know if we will hit the wall or not (and thus stop at destination). Both of the above solutions return true as soon as the destination is reached without considering whether the ball can stop or not.

6
Show 1 reply
Reply
Share
Report
wds8807's avatar
Read More

Regardless of the running time, the DFS code is so messy.

8
Reply
Share
Report
s961206's avatar
Read More

Why the running time of DFS is O(M*N)?

5
Show 3 replies
Reply
Share
Report
Han_V's avatar
Read More

I've implemented BFS as my first idea yet still I don't understand why tests make DFS fail due to TL. BFS in this case is more efficient yet they have same worst case time complexity so to be honest I don't necessarily agree with this decision.

5
Show 1 reply
Reply
Share
Report
utsav_popli's avatar
Read More

Seems like the use case:
[[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]]
[0,4]
[1,2]

is invalid.

Leetcode expected output: True.
In my opinion this should be: False. As the ball can keep rolling

8
Show 9 replies
Reply
Share
Report
xguo-Will's avatar
Read More

@vinod23
My dfs solution just got accepted.
Share my code and comments:

// dfs solution
class Solution {
    private int[] dr;
    private int[] dc;
    private int[][] MAZE;
    private int R;
    private int C;
    private int[] dest;
    private boolean res;
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        dr = new int[]{-1, 1, 0, 0}; // u d l r
        dc = new int[]{0, 0, -1, 1}; // u d l r
        MAZE = maze;
        R = maze.length;
        C = maze[0].length;
        dest = destination;
        res = false;
        
        // doesn't care the initial direction parameter
        dfs(-1, start, new boolean[R][C]);
        return res;
    }
    
    private void dfs(int dir, int[] start, boolean[][] visited) {
        int r = start[0], c = start[1];
        if (Arrays.equals(start, dest)) {
            res = true;
            return;
        } 
        if (visited[r][c]) return;
        visited[r][c] = true;
        // up down left right
        for (int i = 0; i < 4; ++i) {
            if (i == dir) continue; // skip the direction that will hit the wall again
            int x = r, y = c;
            while (isValid(new int[]{x + dr[i], y + dc[i]})) {
                x += dr[i];
                y += dc[i];
            }
            dfs(i, new int[]{x, y}, visited);
        }
    }
    
    // return true if the coord is valid and maze[coord] == 0;
    private boolean isValid(int[] coord) {
        int r = coord[0];
        int c = coord[1];
        if (r < 0 || r >= R || c < 0 || c >= C) return false; 
        if (MAZE[r][c] == 1) return false;
        return true;
    }
}

4
Reply
Share
Report
KaitoKid56's avatar
Read More

I have a dumb question, can anyone answer this, please?

Let's say we come up with the DFS approach in the interview for this very problem and if the interviewer says "Come up with an approach that takes the minimum path", should we do BFS? But both of the approaches take same time and space complexities, right?

2
Reply
Share
Report

You don't have any submissions yet.

490/1883
Contribute
|||
Saved
#451 Sort Characters By Frequency
Medium
#452 Minimum Number of Arrows to Burst Balloons
Medium
#453 Minimum Moves to Equal Array Elements
Easy
#454 4Sum II
Medium
#455 Assign Cookies
Easy
#456 132 Pattern
Medium
#457 Circular Array Loop
Medium
#458 Poor Pigs
Hard
#459 Repeated Substring Pattern
Easy
#460 LFU Cache
Hard
#461 Hamming Distance
Easy
#462 Minimum Moves to Equal Array Elements II
Medium
#463 Island Perimeter
Easy
#464 Can I Win
Medium
#465 Optimal Account Balancing
Hard
#466 Count The Repetitions
Hard
#467 Unique Substrings in Wraparound String
Medium
#468 Validate IP Address
Medium
#469 Convex Polygon
Medium
#470 Implement Rand10() Using Rand7()
Medium
#471 Encode String with Shortest Length
Hard
#472 Concatenated Words
Hard
#473 Matchsticks to Square
Medium
#474 Ones and Zeroes
Medium
#475 Heaters
Medium
#476 Number Complement
Easy
#477 Total Hamming Distance
Medium
#478 Generate Random Point in a Circle
Medium
#479 Largest Palindrome Product
Hard
#480 Sliding Window Median
Hard
#481 Magical String
Medium
#482 License Key Formatting
Easy
#483 Smallest Good Base
Hard
#484 Find Permutation
Medium
#485 Max Consecutive Ones
Easy
#486 Predict the Winner
Medium
#487 Max Consecutive Ones II
Medium
#488 Zuma Game
Hard
#489 Robot Room Cleaner
Hard
#490 The Maze
Medium
#491 Increasing Subsequences
Medium
#492 Construct the Rectangle
Easy
#493 Reverse Pairs
Hard
#494 Target Sum
Medium
#495 Teemo Attacking
Easy
#496 Next Greater Element I
Easy
#497 Random Point in Non-overlapping Rectangles
Medium
#498 Diagonal Traverse
Medium
#499 The Maze III
Hard
#500 Keyboard Row
Easy